package advance.day02;

import java.util.LinkedList;

/**
 * 描述：
 *      指定滑动窗口的大小，获取数组中所有窗口的最大值
 *      此题中的滑动窗口规则：窗口的头节点存放的是此窗口中的最大值的索引，并且从左到右的顺序是从大到小
 * @author hl
 * @version 1.0
 * @date 2020/11/5 16:49
 */
public class SlidingWindowMaxArray {
    /**
     *  获取
     * @param arr
     * @param w     窗口的大小
     * @return
     */
    public static int[] getMaxWindow(int[] arr, int w){
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        LinkedList<Integer> qmax = new LinkedList<>();//使用双端队列构建滑动窗口
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);
            if (qmax.peekFirst() == i - w) {//判断窗口的第一个元素是否过期
                qmax.pollFirst();//过期移除
            }
            if (i >= w - 1) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }
    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {4,3,5,4,3,3,6,7};
        printArray(getMaxWindow(arr, 3));

    }
}
